Wireless cellular telecommunications systems, wire-line telecommunications systems, and the Internet are well-known examples of so-called fixed infrastructure networks. These types of networks are characterized in part by their use of a fixed infrastructure (e.g., wireless base stations, central offices, local loops, routers and the like) and the ability to leverage a known network topology (e.g., in making routing decisions among network nodes). Despite their many advantages, such fixed networks can be expensive to upgrade and can be uneconomical where the number of users is minimal (see, for example, J. Li et al., “A Scalable Location Service for Geographic Ad Hoc Routing”, Proceedings ACM/IEEE Mobicom, pp. 120-130, August 2000, which is hereby incorporated by reference). In contrast, well-known ad hoc networks do not utilize a fixed infrastructure instead utilizing a variable infrastructure which changes as a function of the devices coming together to form the particular ad hoc network. As will be appreciated, ad hoc networks offer increased flexibility and decreased fixed investments to implement (see, for example, Li et al., supra).
An important application in either fixed infrastructure networks or ad hoc networks is so-called “location tracking” which is the ability to locate particular devices (e.g., a node) throughout the network. Location tracking arises in several contexts in mobile networking. For example, location-based routing algorithms have been proposed to reduce the amount of data transferred in computing a path in ad hoc networks (see, for example, Y. B. Ko et al., “Location-Aided Routing (LAR) in Mobile Ad hoc Networks”, Proceedings ACM/IEEE Mobicom, pp. 66-75, October 1998, which is hereby incorporated by reference). Further, well-known cellular applications such as fleet tracking and emergency response systems rely on location information in delivering their respective cellular services. As such, the accuracy of the location information is central to the performance of all these applications whether being delivered via a fixed network or ad hoc network.
There exist a number of well-known location tracking techniques. For example, triangulation is the well-known technique of locating a particular mobile device through the knowledge of the angle of arrival of signals at the to-be-located mobile device from three other devices, where the locations of the three other devices are known. Trilateration is the well-known technique of locating a particular mobile device by determining the distance of the to-be-located mobile device from at least three reference points whose precise location is known. For example, the three reference points might be three other mobile devices in proximity to the to-be-located mobile device. In terms of locating a cellular telephone, two primary forms of trilateration are used in conventional, cellular communications. The first form of trilateration is performed by the cellular network itself using its network infrastructure; in particular, the network uses the known locations of each base station within its infrastructure to locate a particular mobile telephone. Specifically, the location of three known base stations in the same geographic location as the to-be-located mobile telephone is used to determine the relative position of such device. The typical locating precision of this technique is approximately in the range of 50 meters to 300 meters.
The second trilateration form conventionally used in locating a particular mobile telephone device within the cellular communications network employs the well-known Global Positioning System (GPS). GPS is a time-synchronized, space-based satellite system that broadcasts spread spectrum codes and consists of a GPS constellation consisting of 24 individual satellites. A ground-based GPS receiver at or near the object to be located (e.g., the cellular telephone device) determines the difference between the time at which each satellite transmits a particular time signal and the time at which such signal is received. Using the calculated time differentials in standard GPS, the object's location is determined typically to within about 100 meters. This accuracy can be further improved upon by using the well-known commercially available Differential GPS, which improves the GPS location accuracy to within 10 meters.
Still other techniques have been proposed for locating mobile devices in the contexts of indoor ad hoc networks. For example, RADAR (see, P. Bahl et al., “RADAR: An In-Building RF-Based User Location and Tracking System”, IEEE Info Com, March 2000, which is hereby incorporated by reference) is a well-known technique for tracking indoor environments where a single fingerprint of an entire region is constructed and the location of a particular node is determined based on the signal strength observed at its location. Further, for example, CRICKET (see, N. B. Priyantha et al., “The CRICKET Location-Support System”, ACM MOBICOM, August 2000, which is hereby incorporated for reference) is another well-known indoor tracking technique where nodes have so-called “listeners” which receive periodic radio and ultrasound signals from base stations in a network. Thereafter, such signals are employed to determine a particular node's location using an estimate of such node's proximity to the base stations. In CRICKET, the objective is to make an association with the closest base station and not to precisely estimate the true position of the mobile node.
In addition to the above-mentioned RADAR and CRICKET techniques, LAR is a reactive routing protocol used in mobile ad hoc networks where all the nodes are aware of their respective locations, see, for example, Y. B. Ko et al., supra. In LAR, the source of a packet session initiates a route request for the destination. This request, in turn, is forwarded by other nodes that lie within a so-called “request region”, such request region being computed by the source from the previous known location and velocity of the destination. In the event that a route reply is not received within a specified timeout, LAR either resorts to a global flooding protocol or gradually expands the request region and repeats the discovery process until the route is computed.
Geographic forwarding is a stateless packet forwarding technique employed in large wireless networks, see, for example, J. Li et al., supra; and C. T. Cheng et al., “SLALOM: A Scalable Location Management Scheme for Large Scale Mobile Ad hoc Networks”, Proceedings of Wireless Communications and Networking Conference, March 2002, which is hereby incorporated by reference. In geographic forwarding, nodes are aware of their respective locations and a packet intended for a destination is forwarded to the destination's location by the intermediate nodes. The intermediate nodes forward the packet to a neighbor node that is determined to be the closest to the destination in terms of a Euclidean distance.
Other location-based techniques include using short-range, peer-to-peer communications in combination with the imposition of particular distance constraints between nodes to identify a location of a particular node (see, for example, L. Doherty, “Algorithms for Position and Data Recovery in Wireless Sensor Networks”, Master's Report, University of California Berkeley, June 2000, which is hereby incorporated by reference). However, Doherty's technique is best suited for centralized execution which presents certain challenges in a distributed network. Another technique detailed in D. Niculescu et al., “Ad hoc Positioning System (APS) Using AOA”, IEEE Infocom, April 2003, which is hereby incorporated by reference, is directed to a node measuring the angle of arrival of signals from various points (where such points have knowledge about their respective locations) and using triangulation to determine the node's location.
As described above, there exist numerous location-based routing and location information techniques employed in wireless or ad hoc communications networks. Central to the above-described techniques, however, is that they primarily attempt to compute a single point location, which may or may not be the true location. Obviously, if the computed single location is incorrect, that information will adversely impact network performance (e.g., data will be forwarded to incorrect nodes, or data may take extended paths leading to dropped packets). Further, such techniques are primarily directed to centralized execution as opposed to a more distributed execution.
Thus, there exists a need for an enhanced location-based routing technique which addresses multiple locations and provides for distributed execution.